Random access memory (“RAM”) is the most common form of integrated circuit memory available in the state of the art. However, RAM devices are not suited for use in systems which process associative data. For example, the well known methodology of sequentially accessing data when addressing the RAM is inefficient for systems involving stored information involving pattern recognition, data compression, natural language recognition, sparse matrix processes, and data-base interrogation. The address associated with the desired stored data may not be known. For this type of data, it is more efficient to interrogate a memory by supplying a compressed subset of the desired data or a code representative of the full data set. The memory responds by indicating either the absence of the desired data set or presence of the data set by issuing a match signal and an associated address in the memory bank for the data set.
Content addressable memory (CAM) cells were developed to have ambiguous and non-contiguous addressing. For associative data search, the entire CAM can be searched in a single clock cycle, giving it a great advantage over the sequential search technique required when using a RAM device.
Content addressable memories (CAMs) compare a search word with a set of stored words. When the search word matches with one or more stored words, an indication is produced in respect of each stored word. A distinguishing characteristic of a CAM is that each stored word is uniquely identified on the basis of the content of the word itself, rather than by its address within the memory array as in conventional digital memories.
A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory elements constitute a stored word. During a match operation, a search word of input data is applied to all the rows, and an indication is produced for each row as to whether or not the search word matches the word stored therein.
Content addressable memory facilitates searches on a conventional indexed random access memory (RAM). The CAM stores a series of “tags” which represent address locations in the RAM. Match operations are performed on the CAM in order to find the locations of data stored in the RAM. When match data is presented to the CAM, the CAM responds with a “tag” representing the address location in RAM containing the desired data. This address location can then be fed to the RAM's address lines in order to access the data.
The most critical path through the CAM is the search cycle; that is, the time from receipt of an input data signal, or code, to the encoder input to determine if the CAM has the desired data set to the time of the output of a match or mismatch indication, and, if a MATCH signal is generated, the MATCH ADDRESS. Depending on the nature of the data, the CAM core memory can contain locations with redundant information. Therefore, a search will result in a MATCH for more than one MATCH ADDRESS. In this event, it is necessary to determine which MATCH ADDRESS is to be selected on a basis of priority.
Another significant problem can take place in the case of a multiple match, i.e., when more than one row of the CAM tries to indicate a match with the match data. If the CAM lines are connected directly to the RAM's address lines, then a multiple match results in more than one RAM address line being asserted simultaneously. The assertion of multiple address lines affects the response-capability of some RAMS and can even be destructive for some RAM's.